/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
    treeHeight = 0;

    is_readonly = false;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	int ret;
	char buffer[1024];
   	
	ret = pf.open(indexname, mode);

    	if(ret != 0)
		return ret;

	if(mode == 'r')
		is_readonly = true;

	if(pf.endPid() != 0)
	{
		ret = pf.read(0, buffer);
		if(ret != 0)
			return ret;

		PageId* root = (PageId*)buffer;
		int* height = (int*)&buffer[HEIGHT_INDEX];

		rootPid = *root;
		treeHeight = *height;
	} else {
		treeHeight = 0;
		rootPid = -1;
	}

	return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	int ret;
		
	if(is_readonly)
	{
		ret = pf.close();
		return ret;
	}

	char buffer[1024];

	int* height = (int*)&buffer[HEIGHT_INDEX];
	*height = treeHeight;

	PageId* root = (PageId*)buffer;
	*root = rootPid;

	ret = pf.write(0, buffer);
	if(ret != 0)
		return ret;
	
	ret = pf.close();
	return ret;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	int ret;

	if(rootPid == -1)
	{
		BTLeafNode new_node;
		ret = new_node.insert(key, rid);
		if(ret != 0)
			return ret;

		ret = new_node.write(pf.endPid(), pf);
		if(ret != 0)
			return ret;

		rootPid = pf.endPid() - 1;
		treeHeight = 1;

		return 0;
	}
	PageId overPid;
	int overKey;

	ret = insertRecur(key, rid, rootPid, treeHeight, overPid, overKey);

	if(ret != 0)
		return ret;

	if(overPid != -1)
	{
		BTNonLeafNode newRoot;
		ret = newRoot.initializeRoot(rootPid, overKey, overPid);

		if(ret != 0)
			return ret;

		rootPid = pf.endPid();
		treeHeight = treeHeight + 1;

		ret = newRoot.write(pf.endPid(), pf);
		if(ret != 0)
			return ret;
	}

	return 0;
}

RC BTreeIndex::insertRecur(int key, const RecordId& rid, PageId root, int height, PageId& overPid, int& overKey)
{
	int ret;
	overPid = -1;
	
	if(height == 1)
	{
		BTLeafNode leaf;
		ret = leaf.read(root, pf);
		if(ret != 0)
			return ret;

		ret = leaf.insert(key, rid);
		if(ret == RC_NODE_FULL)
		{
			BTLeafNode sibling;
			int siblingKey;

			ret = leaf.insertAndSplit(key, rid, sibling, siblingKey);
			if(ret != 0)
				return ret;

			PageId next = leaf.getNextNodePtr();
			leaf.setNextNodePtr(pf.endPid());
			sibling.setNextNodePtr(next);

			overPid = pf.endPid();
			overKey = siblingKey;

			sibling.write(pf.endPid(), pf);
			leaf.write(root, pf);

			return 0;
		} else if(ret != 0) {
			return ret;
		} else {
			leaf.write(root, pf);

			return 0;
		}
	}

	BTNonLeafNode node;
	ret = node.read(root, pf);
	if(ret != 0)
		return ret;

	PageId child;
	ret = node.locateChildPtr(key, child);
	if(ret != 0)
		return ret;

	PageId resPid;
	int resKey;

	ret = insertRecur(key, rid, child, height - 1, resPid, resKey);
	if(ret != 0)
		return ret;

	if(resPid != -1)
	{
		ret = node.insert(resKey, resPid);
		if(ret == RC_NODE_FULL)
		{
			BTNonLeafNode sibling;
			int midKey;

			ret = node.insertAndSplit(resKey, resPid, sibling, midKey);
			if(ret != 0)
				return ret;

			overKey = midKey;
			overPid = pf.endPid();

			sibling.write(pf.endPid(), pf);
			node.write(root, pf);

			return 0;
		} else if(ret != 0) {
			return ret;
		} else {
			node.write(root, pf);

			return 0;
		}
	}
	return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	int ret;

	PageId leafPid;

	if(treeHeight == 1)
	{
		leafPid = rootPid;
	} else {
		ret = locateLeaf(searchKey, treeHeight, rootPid, leafPid);
		if(ret != 0)
			return ret;
	}

	BTLeafNode leafNode;
	ret = leafNode.read(leafPid, pf);
	if(ret != 0)
		return ret;
	
	int eid;
	ret = leafNode.locate(searchKey, eid);
	if(ret != 0)
		return ret;

	cursor.pid = leafPid;
	cursor.eid = eid;

	return 0;
}

RC BTreeIndex::locateLeaf(int searchKey, int height, PageId root, PageId& leaf)
{
	int ret;

	BTNonLeafNode rootNode;
	ret = rootNode.read(root, pf);

	if(ret != 0)
		return ret;

	PageId next;
	ret = rootNode.locateChildPtr(searchKey, next);
	if(ret != 0)
		return ret;

	if(height == 2)
	{
		leaf = next;
		return 0;	
	}

	return locateLeaf(searchKey, height - 1, next, leaf);
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	int ret;

	BTLeafNode leafNode;
	ret = leafNode.read(cursor.pid, pf);

	if(ret != 0)
		return ret;

	ret = leafNode.readEntry(cursor.eid, key, rid);
	if(ret != 0)
		return ret;

	if(cursor.eid + 1 >= leafNode.getKeyCount())
	{
		cursor.pid = leafNode.getNextNodePtr();
		cursor.eid = 0;
	} else {
		cursor.eid = cursor.eid + 1;
	}

	return 0;
}
